function search(A, target) {
    if(!A || !A.length){
        return -1
    }
    // write your code here
    let start = 0, end = A.length - 1, mid = -1;
    while (start + 1 < end) {
        mid = Math.floor(start + (end - start) / 2);
        if (A[mid] > A[A.length - 1]) {//上半边
            if (A[mid] === target) {
                return mid
            } else if (A[mid] > target && target >= A[0]) {//易错点
                end = mid
            } else {
                start = mid
            }
        } else {//下半边
            if (A[mid] === target) {
                return mid
            } else if (A[mid] < target && target <= A[A.length - 1]) {//易错点
                start = mid
            } else {
                end = mid
            }
        }
    }
    if (A[start] === target) {
        return start
    }
    if (A[end] === target) {
        return end
    }
    return -1
}

console.log(search([],5))
console.log(search([6,8,9,1,3,5],5))
console.log(search([4, 5, 1, 2, 3],1))
console.log(search([4, 5, 1, 2, 3],0))